package Algorithm.Tree;

/**
 * @Author cj
 * @Date 2022/1/17 20:52
 */
public class morris {

    static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int val) {
            this.value = val;
        }
    }

    public static void morris1(Node head) {
        if (head == null) {
            return;
        }
        Node mostRight = null;
        while (head != null) {
            mostRight = head.left;
            if (mostRight != null) {
                // 找到最右节点
                while (mostRight.right != null && mostRight.right != head) {
                    mostRight = mostRight.right;
                }
                // 此时mostRight已指向最右节点
                if (mostRight.right == head) {
                    mostRight.right = null;
                } else { // mostRight.right指向null
                    mostRight.right = head;
                    head = head.left;
                    continue;
                }
            }
            // mostRight.right指向head或head没有左子树
            head = head.right;
        }
    }

    public static void morrisPre(Node head) {
        if (head == null) {
            return;
        }
        Node mostRight = null;
        while (head != null) {
            mostRight = head.left;
            if (mostRight != null) {
                // 找到最右节点
                while (mostRight.right != null && mostRight.right != head) {
                    mostRight = mostRight.right;
                }
                // 此时mostRight已指向最右节点
                if (mostRight.right == head) { // mostRight.right指向head
                    mostRight.right = null;
                } else { // mostRight.right指向null
                    mostRight.right = head;
                    System.out.print(head.value + " ");
                    head = head.left;
                    continue;
                }
            } else {
                System.out.print(head.value + " ");
            }
            // mostRight.right指向head或head没有左子树
            head = head.right;
        }
        System.out.println();
    }

    public static void morrisInorder(Node head) {
        if (head == null) {
            return;
        }
        Node mostRight = null;
        while (head != null) {
            mostRight = head.left;
            if (mostRight != null) {
                // 找到最右节点
                while (mostRight.right != null && mostRight.right != head) {
                    mostRight = mostRight.right;
                }
                // 此时mostRight已指向最右节点
                if (mostRight.right == head) { // mostRight.right指向head
                    mostRight.right = null;
                } else { // mostRight.right指向null
                    mostRight.right = head;
                    head = head.left;
                    continue;
                }
            }
            // mostRight.right指向head或head没有左子树
            System.out.print(head.value + " ");
            head = head.right;
        }
        System.out.println();
    }

    public static void morrisPos(Node head) {
        if (head == null) {
            return;
        }
        Node mostRight = null, stillHead = head;
        while (head != null) {
            mostRight = head.left;
            if (mostRight != null) {
                // 找到最右节点
                while (mostRight.right != null && mostRight.right != head) {
                    mostRight = mostRight.right;
                }
                // 此时mostRight已指向最右节点
                if (mostRight.right == head) {
                    mostRight.right = null;
                    // 逆序打印左子树右边界
                    printEdge(head.left);
                } else { // mostRight.right指向null
                    mostRight.right = head;
                    head = head.left;
                    continue;
                }
            }
            // mostRight.right指向head或head没有左子树
            head = head.right;
        }
        // 逆序打印整棵树右边界
        printEdge(stillHead);
        System.out.println();
    }

    public static void printEdge(Node head) {
        if (head == null) {
            return;
        }
        Node tail = reverseEdge(head);
        Node cur = tail;
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.right;
        }
        reverseEdge(tail);
    }

    private static Node reverseEdge(Node from) {
        Node pre = null, next = null;
        while (from != null) {
            next = from.right;
            from.right = pre;
            pre = from;
            from = next;
        }
        return pre;
    }

}
